package 翻转字符串里的单词;

public class Solution {

    /*
    给你一个字符串 s ，请你反转字符串中 单词 的顺序。
    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
    返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
    注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     */
    public String reverseWords(String s) {
        // 去除多余的空格
        StringBuilder sb = removeBlank(s);
        // 反转整个字符串
        reverseWords(sb, 0, sb.length() - 1);
        // 反转每一个单词
        String result = reversePreWord(sb);
        return result;
    }

    public StringBuilder removeBlank(String s) {
        // 遇到空格就删除空格，出现： 单词1（）单词2。这种情况的时候需要为两个单词添加一个空格
        // 添加空格需要保证，这个空格是在两个单词之间 -->
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        boolean flag = false; // 标记“单词1”是否存在
        for (int i = 0; i < len; i++) {
            char c1 = s.charAt(i);
            // 为两个单词添加一个空格，满足条件如下:
            // ①当前字符是空格②下一个字符不是空格③当前字符的前面已经出现过单词字符
            char c2 = ' ';
            if (i < len - 1)
                c2 = s.charAt(i + 1);
            if (c1 == ' ' && c2 != ' ' && flag) {
                sb.append(" ");
            }
            // 将单词抽取到sb中
            if (c1 != ' ') {
                sb.append(c1);
                flag = true;
            }
        }
        return sb;
    }

    public void reverseWords(StringBuilder sb, int left, int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, temp);
            left++;
            right--;
        }
    }

    public String reversePreWord(StringBuilder sb) {
        int left = 0;
        int right = 0;
        int len = sb.length();
        for (int i = 0; i < len; i++) {
            if (sb.charAt(i) == ' ') {
                reverseWords(sb, left, right - 1);
                left = right + 1;
            }
            right++;
        }
        // 处理最后一个单词
        reverseWords(sb, left, right - 1);
        return sb.toString();
    }

}

